Algorithme du simplexe

Ne pas confondre avec la méthode de Nelder-Mead qui s'applique aux problèmes d'optimisation non linéaires.

L'algorithme du simplexe est un algorithme de résolution des problèmes d'optimisation linéaire. Il a été introduit par George Dantzig à partir de 1947. C'est probablement le premier algorithme permettant de minimiser une fonction sur un ensemble défini par des inégalités^[1]. De ce fait, il a beaucoup contribué au démarrage de l'optimisation numérique. L'algorithme du simplexe a longtemps été la méthode la plus utilisée pour résoudre les problèmes d'optimisation linéaire. Depuis les années 1985-90, il est concurrencé par les méthodes de points intérieurs, mais garde une place de choix dans certaines circonstances (en particulier si l'on a une idée des contraintes d'inégalité actives en la solution).

Le nom de l'algorithme est dérivé de la notion de simplexe et a été suggéré par Motzkin^[2]. En réalité, l'algorithme n'utilise pas de simplexes, mais certaines interprétations de l'ensemble admissible du problème renvoient au concept de simplexe.

Connaissances supposées : l'algèbre linéaire, le calcul différentiel, le vocabulaire de l'optimisation mathématique.